package com.jd.oneday.month3;

/**
 * @author liulonghui10
 * 1.实现单链表反转
 * 2.实现两个有序链表合并成一个有序链表
 */


/**
 * 管理链表的类
 */

public class Day10_LinkedListReverse {

    private LinkedListNode node = new LinkedListNode(0, "", 0);


    public LinkedListNode getNode() {
        return node;
    }


    /**
     * 两个有序链表合并成一个有序链表
     *
     * @param head1 需要合并有序的单链表1
     * @param head2 需要合并的有序单链表2
     * @return
     */

    public LinkedListNode MergeLinkedList(LinkedListNode head1, LinkedListNode head2) {

        //判断是否都为空链表
        if (head1 == null && head2 == null) {
            System.out.println("这是两个空链表");
            return null;
        }
        //如果head1为空链表  则返回head2
        if (head1.next == null) {
            return head2;
        }
        //如果head2为空链表  则返回head1
        if (head2.next == null) {
            return head1;
        }
        //因为头部节点不能动，所以需要辅助指针
        LinkedListNode temp1 = head1.next;
        LinkedListNode temp2 = head2.next;
        //创建一个新头节点
        LinkedListNode pre = null;
        //创建一个新尾节点
        LinkedListNode next = null;
        //判断两个链表节点  那个节点小就存到新的头节点里
        if (temp1.id <= temp2.id) {
            pre = temp1;
            next = temp1;
            temp1 = temp1.next;
        } else {
            pre = temp2;
            next = temp2;
            temp2 = temp2.next;
        }

        while (true) {
            //两个链表只要一个为空，就退出循环
            if (temp1 == null || temp2 == null) {
                break;
            }
            //判断两个链表节点  那个节点小就存到新的尾节点里
            if (temp1.id <= temp2.id) {
                next.next = temp1;
                next = temp1;
                temp1 = temp1.next;

            } else {
                next.next = temp2;
                next = temp2;
                temp2 = temp2.next;
            }

        }
        //判断将不是空的链表剩余节点添加进新链表的尾节点后面
        if (temp1 == null) {
            next.next = temp2;
        } else {
            next.next = temp1;
        }
        return pre;
    }

    /**
     * 遍历
     */
    public void List1(LinkedListNode list) {

        //判断链表是否为空
        if (list == null) {
            System.out.println("这是一个空链表");
            return;
        }
        //因为头部节点不能动，所以需要一个辅助指针
        LinkedListNode temp = list;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }


    /**
     * @param head 需要反转的链表
     */
    public void linkedListReverse(LinkedListNode head) {
        //是个空链表或者只有一个节点   无需反转
        if (head.next == null || head.next.next == null) {
            System.out.println("无需反转");
            return;
        }

        //准备一个新的链表头    将反转的节点暂时存放在新的链表上
        LinkedListNode newNode = new LinkedListNode(0, "", 0);
        //因为头部节点不能动，所以需要一个辅助指针
        LinkedListNode temp = head.next;
        //暂时保存temp.next
        LinkedListNode next = null;
        while (true) {
            if (temp == null) {
                break;
            }
            //将节点先保存下来
            next = temp.next;
            //将新链表节点的指向移到 新加入最新节点 的指向
            temp.next = newNode.next;
            //将temp节点链接到新链表上
            newNode.next = temp;
            //链表节点后移
            temp = next;
        }
        //将reverseHead指向node
        node.next = newNode.next;
    }

    /**
     * @param head 添加到链表中的节点
     */
    public void add(LinkedListNode head) {
        //因为头部节点不能动，所以需要一个辅助指针
        LinkedListNode temp = node;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = head;
    }


    /**
     * 遍历
     */
    public void List() {

        //判断链表是否为空
        if (node.next == null) {
            System.out.println("这是一个空链表");
            return;
        }
        //因为头部节点不能动，所以需要一个辅助指针
        LinkedListNode temp = node;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
            System.out.println(temp);
        }
    }

}
